P6156 简单题

i=1nj=1n(i+j)kf(gcd(i,j))gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j)

显然 f(i)=μ2(i)f(i)=\mu^2(i)

i=1nj=1n(i+j)kμ2(gcd(i,j))gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k \mu^2(\gcd(i,j)) \gcd(i,j)

d=1ni=1nj=1n[gcd(i,j)=d](i+j)kμ2(d)d\sum_{d=1}^n\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=d](i+j)^k \mu^2(d) d

d=1ndk+1μ2(d)i=1ndj=1nd[gcd(i,j)=1](i+j)k\sum_{d=1}^n d^{k+1}\mu^2(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i,j)=1](i+j)^k

d=1ndk+1μ2(d)t=1ndμ(t)tki=1ntdj=1ntd(i+j)k\sum_{d=1}^n d^{k+1}\mu^2(d)\sum_{t=1}^{\lfloor \frac{n}{d} \rfloor}\mu(t)t^k\sum_{i=1}^{\lfloor \frac{n}{td} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{td} \rfloor}(i+j)^k

d=1nt=1nd(dt)kμ2(d)μ(t)di=1ntdj=1ntd(i+j)k\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor}(dt)^{k}\mu^2(d)\mu(t)d\sum_{i=1}^{\lfloor \frac{n}{td} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{td} \rfloor}(i+j)^k

T=td , S(n)=i=1nj=1n(i+j)kT=td ~,~ S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k

T=1nS(nT)TkdTdμ2(d)μ(Td)\sum_{T=1}^n S( \lfloor \frac{n}{T} \rfloor) T^k\sum_{d|T} d\mu^2(d)\mu(\frac{T}{d})

f(n)=dndμ2(d)μ(nd)f(n)=\sum_{d|n} d\mu^2(d)\mu(\frac{n}{d})

T=1nS(nT)Tkf(T)\sum_{T=1}^n S( \lfloor \frac{n}{T} \rfloor) T^kf(T)

推导的部分就结束了。


S(n)S(n)换一种写法:

S(n)=i=12naiikS(n)=\sum_{i=1}^{2n} a_ii^k

其中 aia_iiki^k 出现的次数。可以发现:

ai={i1in2ni+1i>na_i=\begin{cases} i-1 & i\le n \\ 2n-i+1 & i>n \end{cases}

再令 t(n)=i=1nj=1ijk=i=1n(ni+1)ikt(n)=\sum_{i=1}^n\sum_{j=1}^i j^k=\sum_{i=1}^n (n-i+1)i^k

对比系数发现: S(n)=t(2n)2t(n)S(n)=t(2n)-2t(n)

另外一个 ff 是一个积性函数,可以线筛。

#include <cstdio>
#define Mod 998244353

const int MAXN = 1e7;
int n , k , cnt , prime[ MAXN + 5 ] , f[ MAXN + 5 ] , s[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

int Quick_pow( int x , int po ) {
    int Ans = 1;
    for( ; po ; po >>= 1 , x = 1ll * x * x % Mod )
        if( po & 1 ) Ans = 1ll * Ans * x % Mod;
    return Ans;
}

void sieve( ) {
    f[ 1 ] = s[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ cnt ] = i;
            s[ i ] = Quick_pow( i , k );
            f[ i ] = i - 1;
        }
        for( int j = 1 ; j <= cnt && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            s[ i * prime[ j ] ] = 1ll * s[ i ] * s[ prime[ j ] ] % Mod;
            if( i % prime[ j ] == 0 ) {
                if( i / prime[ j ] % prime[ j ] != 0 )
                    f[ i * prime[ j ] ] = ( 1ll * -prime[ j ] * f[ i / prime[ j ] ] % Mod + Mod ) % Mod;
                break;
            } 
            f[ i * prime[ j ] ] =  1ll * f[ i ] * f[ prime[ j ] ] % Mod;
        }
    } 
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        f[ i ] = ( 1ll * f[ i ] * s[ i ] % Mod + f[ i - 1 ] ) % Mod;
        s[ i ] = ( s[ i ] + s[ i - 1 ] ) % Mod;
    }
    for( int i = 2 ; i <= MAXN ; i ++ )
        s[ i ] = ( s[ i ] + s[ i - 1 ] ) % Mod;
}

int Sum( int n ) {
    return ( ( s[ 2 * n ] - 2ll * s[ n ] ) % Mod + Mod ) % Mod;
}

int Solve( int n ) {
    int Ans = 0;
    for( int l = 1 , r ; l <= n ; l = r + 1 ) {
        r = n / ( n / l );
        Ans = ( Ans + 1ll * ( f[ r ] - f[ l - 1 ] + Mod ) % Mod * Sum( n / l ) % Mod ) % Mod;
    }
    return Ans;
}

int main( ) {
    long long t;
    scanf("%d %lld",&n,&t); k = t % ( Mod - 1 );
    sieve( );
    printf("%d\n", Solve( n ) );
    return 0;
}